二分法 Bisection Method
方程式の解を求める手法の一つ、区間を初期値として与えて、領域を二分探索的に狭めていき符号が切り替わる部分を求める形で解を求める。
考え方はすごいシンプル
連続な関数$ f(x)の符号が正から負になる区間が存在した場合、当然ながらその区間で関数$ f(x)は$ f(x) = 0となる点、つまるところ解を持つはずである。なので、区間の両端における$ f(x)の符号が異なるように区間を縮めていけば$ f(x) = 0となる点へと近づいていくことが考えられる。
ということで$ f(x_0),f(x_1)が異なる符号になるような区間$ \lbrack a,b \rbrackを初期値として与えてあげます(どうやってそれを作るのかは置いておいて)。
次に中間点となる$ x_Mを作り$ f(x_M)の符号を求めます。この時、$ f(x_M)の符号は$ f(a),f(b)のどちらかと反対の関係にあり、$ x_Mと符号が異なる端点で新たな小さな区間を生成します。
例えば、$ f(x_M)と$ f(a)が異なる符号であれば$ \lbrack a,x_M\rbrackを作り、一方で$ f(b)と異なる符号であった場合は$ \lbrack x_M,b \rbrackという感じに新たな区間を作る。
これを繰り返し行っていくと端点の符号が異なったまま区間を小さくできるため、（無限にやるなら）最終的に解$ f(x) = 0へと収束していく。
こんな感じの手法
精度は分割回数$ nに対して
$ \frac{x_1 - x_0}{2^n}
良いところ
方程式$ f(x)が連続かつ、ちゃんと初期値の両端の関数値の符号がちゃんと異なっているという条件が満たされていれば必ず解に収束する
導関数等求める必要がなく、関数だけでよい(ニュートン法と比較しての利点）
悪いところ
ニュートン法とかに比べると収束が遅い
そもそも初期値を符号が異なるようにしないといけない
解が必ず得られるという安定性で選ばれているらしい